package other;

public class findTargetSumWays_494 {
    public int findTargetSumWays(int[] nums, int target) {
        //数组最终分为➕组(left)和➖组(right)
        //即left-right=target
        //left+right=sum
        //得left=(sum+target)/2
        int sum = 0;
        for (int num : nums)
            sum += num;
        //如果target的绝对值大于sum，那么是没有方案的
        if (Math.abs(target) > sum)
            return 0;
        if ((sum + target) % 2 != 0)
            return 0;   //说明要求的left为小数，无解决方案

        int bigSize = (sum + target) / 2;
        int[] dp = new int[bigSize + 1];  //dp[i] 为填满容量为i 背包 的方案总数
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {  //遍历物品
            for (int j = bigSize; j >= nums[i]; j--) {
                dp[j] = dp[j] + dp[j - nums[i]];
                //放或者不放
            }
        }
        return dp[bigSize];
    }
}
